#ifndef LINKLIST_H__
#define LINKLIST_H__


/******************************************************************************
函数索引(推荐使用V开头的宏定义函数)：

基本函数：
	1、 ListManageInit			：初始化链表管理器
	2、 ListLength	  			：获取链表节点数量 
获取函数：
	1、 vListPeekHead			：获取头指针
	2、 vListPeekTail			：获取尾指针
	3、 vListPeekNext			：获取下一个节点指针
	4、 vListPeekPrev 			：获取上一个节点指针 
	5、 vListPeekItem 			：获取节点所在的索引位置
	6、	vListPeekIndex			：获取索引位置的节点指针，索引可以是负数，表示从后往前数 
插入函数：
	1、 vListPutTail			：新数据插入到尾部
	2、 vListPutHead			: 新数据插入到开头
	3、 vListInsertBeforItem 	：新数据插入到指定节点的前边
	4、 vListInsertAfterItem	：新数据插入到指定节点的后边 
	5、 vListInsertBeforIndex	：新数据插入到指定索引前边，索引可以是负数，表示从后往前数  
	6、 vListInsertAfterIndex	：新数据插入到指定索引后边，索引可以是负数，表示从后往前数  
删除函数：（注意，删除的节点需要自行free） 
	1、vListPopHead				：获取头节点指针并删除
	2、vListPopEnd				：获取尾节点指针并删除
	3、vListRemoveItem			：删除指定节点
	4、vListPopIndex			：获取制定索引的节点并删除，索引可以是负数，表示从后往前数  
交换函数：
	1，vListSwitchItems			：交换两个节点 
	2、vListSwitchIndex			：交换两个索引的节点 
排序函数：
	1、ListSort

******************************************************************************/

/******************************************************************************
关键用法
1、定义新节点结构体，第一项类型必须是 ListNode ： 
	typedef struct {
		ListNode node;		//第一项必须是 ListNode类型的变量 
		int a; 				//后边可以添加其他类型成员 
	} myNode;
	注意：如果新结构体的第一个元素不是ListNode类型，则使用方法参看第七条！！！ 
2、定义链表管理器变量，并初始化 ：	
	ListManage listManage;			//定义链表管理器变量 
	ListManageInit(&listManage);	//初始化 
   分配自定义节点的内存地址，并赋值 ： 
    myNode* node1 = (myNode*)malloc(sizeof(myNode));
    node1->a = 1; 
    myNode* node2 = (myNode*)malloc(sizeof(myNode));
    node2->a = 2;
    myNode* node3 = (myNode*)malloc(sizeof(myNode));
    node3->a = 3;
    myNode* node4 = (myNode*)malloc(sizeof(myNode));
    node4->a = 4;
3、插入节点方法：(注意：不要重复插入同样的节点) 
	vListPutTail(&listManage, node1); 					//插入到链表尾部 
	vListPutHead(&listManage, node2); 					//插入到链表头部 
	vListInsertAfterItem(&listManage, node1, node3);	//插入到node1之前	 
	vListInsertBeforIndex(&listManage, -1, node4); 		//插入到最后一个节点之前	 
   其他函数类同  
4、遍历
	从头遍历(注意：pln类型尽量直接定义成myNode*)：
	myNode *pln;
  	for (pln = vListPeekHead(&listManage); pln != NULL; pln = vListPeekNext(pln)) 
  	{//do Something }
  	从尾遍历：
	myNode *pln;
  	for (pln = vListPeekTail(&listManage); pln != NULL; pln = vListPeekPrev(pln)) 
  	{//do Something }    
5、删除函数（弹出的节点注意强制转换成自己的类型，否则释放内存会只释放一部分） 
	myNode *pln1 = vListPopHead(&listManage);				//删除头节点 
	myNode *pln2 = vListPopIndex(&listManage,1);			//删除索引为1位置的节点
	vListRemoveItem(&listManage,node3);	 					//直接删除节点 node3
	
	重点！！！！删除后，如果不再使用，请务必释放空间 
	if(pln1 != NULL)
	{free(pln1);  pln1 = NULL;}
	if(pln2 != NULL)
	{free(pln2);  pln2 = NULL;}
	if(node3 != NULL)
	{free(node3);  node3 = NULL;}
6、 排序函数
	先在顶层文件自定义FUN_COMPARE格式的函数，FUN_COMPARE是函数指针类型 
	char scoreCompare(ListNode *node1, ListNode *node2)
	{
		//比较任何你想比较的结构体成员 
		return ((myNode*)node1)->a - ((myNode*)node2)->a;	
	}  
	然后调用ListSort函数进行排序
	ListSort(&listManage,TRUE,scoreCompare) ;//从小到大排序
	ListSort(&listManage,FALSE,scoreCompare) ;//从打到校排序 
7、 如果新结构体的第一个元素不是ListNode类型，则使用方法如下：
 	typedef struct {		
		int a; 				//后边可以添加其他类型成员 
		ListNode node;		//ListNode类型不在第一条 
	} my_Node;
	my_Node* node_1 = (my_Node*)malloc(sizeof(my_Node)); //新节点 
	(1)、若把节点当成参数传入到链表函数时，需要如下操作：
		vListPutTail(&listManage, &(node_1->node)); //把 node_1的node的成员地址传入函数 
	(2)、函数返回值为 ListNode*类型，转换成 my_Node，需要如下操作：
		ListNode* pln = vListPeekHead(&listManage);
		my_Node* getNode = container_of(pln, my_Node, node); //根据成员地址反推结构体指针 
	(3)、故此，遍历函数需要这样写：
		从头遍历(注意：pln类型尽量直接定义成ListNode*：
		ListNode *pln;		//遍历的成员地址 
		my_Node *getNode;	//成员地址对应的结构体地址 
	  	for (pln = vListPeekHead(&listManage); pln != NULL; pln = vListPeekNext(pln)) 
	  	{
	  		getNode = container_of(pln, my_Node, node); //根据成员指针反推结构体指针 
		  	//do Something 
		}
	(4)、总结：	传入的参数如果是 ListNode*类型，则参数改成 &(node_1->node)；
				若已知结构体ListNode成员的指针，则调用 container_of宏定义获取结构体指针 
				其中container_of的参数意义参考下边的函数说明 
	 
	 
	 
******************************************************************************/

/******************************************************************************
非必要的说明： 
	由于原函数对类型控制比较强，自定义节点结构体后必须强制类型转换才能使用函数，
	故在这里通过宏定义重新强制转换一次，让所有函数前边都加v重新命名，让调用更加方便
例如：
	原函数声明如下： 
	ListNode *ListPeekPrev (ListNode *listNode)
	重新宏定义后声明如下（返回值强制为void*，输入参数强制为ListNode*）： 
	#define vListPeekPrev(listNode)	(void *)ListPeekPrev((ListNode *)(listNode))
	
	若node1是类型为myNode*类型的指针，其中myNode第一个元素包含ListNode 
	则原函数调用时，必须强制类型转换： 
	ListPutTail(&listManage, (ListNode *)node1);
	而宏定义调用简化为：
	vListPutTail(&listManage, node1); 
其实：
	 把原函数定义的时候改成这样也能起到同样效果，只是隐藏了指针类型会产生一点点迷惑：
	 void *ListPeekPrev (void *listNode);
	 在函数内部，把参数强制为 ListNode*，返回值强制为 void *
******************************************************************************/


	

//双向链表节点的结构体 
typedef struct Link_s 
{
    struct Link_s *next;	//节点指向下一个元素指针 
    struct Link_s *prev;	//节点指向上一个元素指针 
} ListNode;

//链表管理器的结构体 
typedef struct list_t{
    struct Link_s *head;	//保存链表头节点 
    struct Link_s *tail;	//保存链表尾节点 
    long Length; 			//保存链表元素个数 
} ListManage;



//定义一些必要的类型 
#ifndef NULL
	#define NULL (void *)0
#endif

#ifndef BOOL
	#define BOOL char
#endif

#ifndef FALSE
	#define FALSE 0
#endif 

#ifndef TRUE
	#define TRUE 1
#endif 

/******************************************************************************
*函数名称：  container_of
*输入参数：  ptr，结构体某个某个成员的指针
*			 type，结构体名字
* 			 member，ptr对应的结构体成员的名字 
*			 注意：type和member即不是变量也不是字符串，只是个名字，
*					因此既不能传入变量，也不能用双引号 
*输出参数：  无 
*返回值  ：  根据输入的成员指针返回结构体的指针 
*功能描述：  根据输入的成员指针返回结构体的指针 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.12.9
******************************************************************************/
#ifndef container_of
	#define container_of(ptr, type, member) \
    ((type *)((size_t)ptr - (size_t)(&(((type *)0)->member))))			
#endif
 
#ifndef offsetof
	#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

/******************************************************************************
*函数名称：  FUN_COMPARE
*输入参数：  待比较的两个结构体成员，
*			 注意：比较的不是ListNode的成员，而是自定义节点的自定义成员
*					实现时此参数必须强制转换成自己的结构体  
*输出参数：  无 
*返回值  ：  比较结果，	正数：第一个节点的某个元素大于第二个；
* 						0：俩节点某个元素相等 ； 
*						负数：第一个节点的某个元素小于第二个；
*功能描述：  比较函数的回调函数指针 ，比较自定义节点某个成员的大小  
*调用方法：  比较自定义节点某个成员的大小 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
typedef int (* FUN_COMPARE)(ListNode *, ListNode *);


/******************************************************************************
*函数名称：  ListManageInit
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数  
*输出参数：  无
*返回值  ：  无
*功能描述：  初始化链表管理器 
*调用方法：  初始化链表管理器，并把数量保存为0 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListManageInit (ListManage *listManage);

/******************************************************************************
*函数名称：  ListLength
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数  
*输出参数：  无
*返回值  ：  无
*功能描述：  获取链表长度 
*调用方法：  获取链表长度 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
long ListLength (ListManage *listManage);

/******************************************************************************
*函数名称：  ListPeekHead
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数  
*输出参数：  无
*返回值  ：  链表头节点指针 。为空，说明 链表无节点 
*功能描述：  获取第头节点，如果为空，则说明链表无节点，也可以用于判断链表状态 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekHead (ListManage *listManage) ;
#define vListPeekHead(listManage)	(void *)ListPeekHead((listManage))

/******************************************************************************
*函数名称：  ListPeekTail
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
*输出参数：  无
*返回值  ：  链表尾节点指针 。为空，说明 链表无节点 
*功能描述：  获取一个尾节点，如果为空，则说明链表无节点，也可以用于判断链表状态 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekTail (ListManage *listManage);
#define vListPeekTail(listManage)	(void *)ListPeekTail((listManage))

/******************************************************************************
*函数名称：  ListPeekNext
*输入参数：  listNode，输入当前节点，用于获取此节点的后续节点 
*输出参数：  无
*返回值  ：  输入节点的后一个节点 。 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekNext (ListNode *listNode);
#define vListPeekNext(listNode)	(void *)ListPeekNext((ListNode *)(listNode))
/******************************************************************************
*函数名称：  ListPeekPrev
*输入参数：  listNode，输入当前节点，用于获取此节点的前一个节点 
*输出参数：  无
*返回值  ：  输入节点的前一个节点 。 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekPrev (ListNode *listNode);
#define vListPeekPrev(listNode)	(void *)ListPeekPrev((ListNode *)(listNode))

/******************************************************************************
*函数名称：  ListPeekItem
*输入参数：  listManage,链表管理器 
**			 listNode，输入当前节点，用于获取此节点的后续节点 
*输出参数：  无
*返回值  ：  返回对应节点在链表中的位置，如果是-1表明没有在链表里边 
*功能描述：  根据节点指针获取节点所在的索引位置 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
long ListPeekItem (ListManage *listManage, ListNode *listNode);
#define vListPeekItem(listManage, listNode)		ListPeekItem((listManage), (ListNode *)(listNode))

/******************************************************************************
*函数名称：  ListPeekIndex
*输入参数：  listManage,链表管理器 
**			 index,获取节点的索引，如果是负数，表明是从后往前搜索，
**			       最后一个数据索引是-1，以此类推 
*输出参数：  无
*返回值  ：  返回对应节点指针，如果为NULL表明没有对应节点 
*功能描述：  获取当前节点的后一个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPeekIndex (ListManage *listManage, long index);
#define vListPeekIndex(listManage, index)	(void *)ListPeekIndex((listManage), (index))

/******************************************************************************
*函数名称：  ListPutTail
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
*			 listNode 将要添加的节点地址 
*输出参数：  无
*返回值  ：  无
*功能描述：  把新节点追加到链表最后 
*调用方法：  插入节点时使用 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListPutTail (ListManage *listManage, ListNode *listNode);
#define vListPutTail(listManage, listNode)	ListPutTail((listManage),(ListNode *)(listNode))

/******************************************************************************
*函数名称：  ListPutHead
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
*			 listNode 将要添加的节点指针
*输出参数：  无
*返回值  ：  无
*功能描述：  把新节点追加到链表最开始，多用于栈链表 
*调用方法：  插入节点时使用 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
void ListPutHead (ListManage *listManage, ListNode *listNode);
#define vListPutHead(listManage, listNode)  ListPutHead((listManage), (ListNode *)(listNode))

/******************************************************************************
*函数名称：  ListInsertBefor
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertBeforItem (ListManage *listManage, ListNode *listNode, ListNode *lnew);
#define vListInsertBeforItem(listManage, listNode, lnew)	ListInsertBeforItem((listManage), (ListNode *)(listNode), (ListNode *)(lnew))

/******************************************************************************
*函数名称：  ListInsertAfterItem 
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之后 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertAfterItem (ListManage *listManage, ListNode *listNode, ListNode *lnew);
#define vListInsertAfterItem(listManage, listNode, lnew)	ListInsertAfterItem((listManage), (ListNode *)(listNode), (ListNode *)(lnew))

/******************************************************************************
*函数名称：  ListInsertBeforIndex
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无  
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertBeforIndex (ListManage *listManage, long index, ListNode *lnew);
#define vListInsertBeforIndex(listManage, index, lnew)	ListInsertBeforIndex((listManage), (index), (ListNode *)(lnew))

/******************************************************************************
*函数名称：  ListInsertAfterIndex
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 listNode，被插入的节点指针
**		   	 lnew，新节点 
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把节点lnew插入到 listNode之前 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListInsertAfterIndex (ListManage *listManage, long index, ListNode *lnew);
#define vListInsertAfterIndex(listManage, index, lnew)	ListInsertAfterIndex((listManage), (index), (ListNode *)(lnew))

/******************************************************************************
*函数名称：  ListPopHead
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
*输出参数：  无
*返回值  ：  链表第一个节点指针 
*功能描述：  获取第一个节点，并删除 
*调用方法：  弹出后，注意释放内存 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.29
******************************************************************************/
ListNode *ListPopHead (ListManage *listManage);
#define vListPopHead(listManage)	(void *)ListPopHead((listManage))

/******************************************************************************
*函数名称：  ListPopEnd
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
*输出参数：  无
*返回值  ：  链表的最后一个节点指针 
*功能描述：  弹出最后一个节点 ，并删除 
*调用方法：  弹出后，注意释放内存 
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPopEnd (ListManage *listManage);
#define vListPopEnd(listManage)	(void *)ListPopEnd((listManage))

/******************************************************************************
*函数名称：  ListRemoveItem
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 listNode，将要删除的节点指针
*输出参数：  无
*返回值  ：  无 。 
*功能描述：  把listNode从链表中删除 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListRemoveItem (ListManage *listManage, ListNode *listNode);
#define vListRemoveItem(listManage,listNode) 	ListRemoveItem((listManage), (ListNode *)(listNode))

/******************************************************************************
*函数名称：  ListPopIndex
*输入参数：  listManage，链表管理器，保存链表的收尾地址和总数 
**			 index,将要被弹出的节点索引 
*输出参数：  无
*返回值  ：  弹出的节点指针。 
*功能描述：  获取index位置的节点，并删除 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
ListNode *ListPopIndex (ListManage *listManage, long index);
#define vListPopIndex(listManage, index)	(void *)ListPopIndex((listManage), (index))

/******************************************************************************
*函数名称：  ListSwitchItems
*输入参数：  node1,node2，将要交换的两个节点 
*输出参数：  无
*返回值  ：  无。 
*功能描述：  交换两个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListSwitchItems (ListManage *listManage, ListNode *node1, ListNode *node2);
#define vListSwitchItems(listManage, node1, node2) 	ListSwitchItems((listManage),(ListNode *)(node1), (ListNode *)(node2))

/******************************************************************************
*函数名称：  ListSwitchIndex
*输入参数：  index1,index2,交换的两个索引位置 
*输出参数：  无
*返回值  ：  无。 
*功能描述：  交换两个节点 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.11.30
******************************************************************************/
void ListSwitchIndex (ListManage *listManage, long index1,long index2);
#define vListSwitchIndex ListSwitchIndex

/******************************************************************************
*函数名称：  ListSort
*输入参数：  listManage，链表管理器
*			 s2b,从小到大排列，TRUE为从小到大，FALSE为从大到小 
*			 fun_compare，返回比较值的函数指针，可以是正数，负数，0
*输出参数：  无
*返回值  ：  无。 
*功能描述：  按照 fun_compare的规则排序链表 
*调用方法：  
*作者    ：  神圣的大喵
*版本    ：  V1.0
*修改时间：  2024.12.3
******************************************************************************/
void ListSort(ListManage *listManage,BOOL s2b, FUN_COMPARE fun_compare);
#define vListSort ListSort

#endif /* LINKLIST_H__ */
